Early inspirations and new directions in functional reactive programming
In 1989, I was a grad student nearing completion at Carnegie Mellon. Kavi Arya gave a talk on “functional animation”, using lazy lists. I was awe-struck with the elegance and power of that simple idea, and I’ve been hooked on functional animation ever since.
At the end of Kavi’s talk, John Reynolds offered a remark, roughly as follows:
You can think of sequences as functions from the natural numbers. Have you thought about functions from the reals instead? Doing so might help with the awkwardness with interpolation.
I knew at once I’d heard a wonderful idea, so I went back to my office, wrote it down, and promised myself that I wouldn’t think about Kavi’s work and John’s insight until my dissertation was done. Otherwise, I might never have finished. A year or so later, at Sun Microsystems, I started working on functional animation, which then grew into functional reactive programming (FRP).
In the dozens of variations on FRP I’ve played with over the last 15 years, John’s refinement of Kavi’s idea has always been the heart of the matter for me.
Lately, I’ve been rethinking FRP yet again, and I’m very excited about where it’s leading me.
The semantic model of FRP has been based on behaviors of infinite duration and, mostly on absolute time. Recently I realized that some problems of non-modular interaction could be elegantly addressed by switching to finite duration and relative time, and by adopting a co-monadic approach.
Upcoming post will explore these ideas.
Raoul Duke:
cool stuff, thank you for being an explorer and forging ahead. it will be very cool when typed fp can come ‘full circle’ and kick actionscript-flash’s butt.
1 December 2008, 12:52 pmconal:
@Raoul: Thanks much for the encouragement. I’m confident that we’ll get there with type & pure fp.
And another relevant favorite:
1 December 2008, 1:50 pmdaryoush:
Would you please elaborate some more on the Kavi Arya and John Reynolds statements.
Thanks
1 December 2008, 6:07 pmconal:
@daryoush:
A sequence can be indexed by natural numbers. In Haskell,
(!!) :: [a] -> Int -> a. When(!!)gets applied to just a list, the result has type:Int -> a, i.e., a function. If the list is known to be infinite, then that function has exactly the same information as the original list. If the list is finite, the function could return ⊥ (in the form of an error message) when indexed beyond its end. In that finite case, there’s some information loss, namely the list’s length.I promised natural numbers but gave you
Int. The list indexing function(!!)really does require a natural, but that distinction by a run-time check rather than a compile-time one.So, finiteness and efficiency aside, we can think of sequences as “functions from the natural numbers”. From this perspective, we might wonder what would “sequences” be like if they didn’t have those gaps between values. What if we filled them in so that they have values corresponding not just to the naturals but to all of the real-values (or rational-valued or …) indices between those naturals?
For animation, this simple idea lets us represent the flow of dynamic quantities without regard to how they’ll be sampled for output. This separation of concerns is terrific for modularity. Continuous flows are much more easily manipulated and combined than their more common discrete counterparts. For instance, given two flows you want to combine in parallel, there’s no awkwardness around the possibility of being sampled at different rates or phases (in other words, defined over different domains).
This value of infinite and continuous models applies not just to time but also to space. See Pan and Pajama for demonstrations.
1 December 2008, 6:36 pmclaus:
Glad to hear about your new directions, Conal! I’ve been worried about compositionality vs time in FRP for quite some time (see, for instance, the slide “Problems with Fran? (2)” in my IFL’#2002 talk).
The way I see it, it all comes down to friction between behaviours and reactivity:
o as long as we only have behaviours without reactivity, the mathematical ideal (time->value) works both as an elegant model and as a straightforward implementation
o once we add reactivity, the ideal still kind-of works, piecewise, between events; there is some friction, but one has to look closely to see it
o once we want to see reactive behaviours as just another first-class kind of behaviours, that particular ideal breaks down:
] either we admit defeat (we cannot reproduce the value of a behaviour just from the behaviour and an arbitrary time in past or future)
] or we try to maintain the illusion at all cost, keeping the entire past history (at least the non-deterministic inputs) and hiding the future history (until the necessary inputs are fixed), thereby inviting all kinds of space-leaks (and since they are part of the semantics, no level of advanced hacking will get rid of all of them)
Programming according to the semantic ideal (time->value) soon becomes painful (user parameter, start times, behaviour aging, splitB, ..), losing sight of the programming ideal (compositional models)
The FunWorlds/FRP experiment tried a very simple alternative approach:
o a behaviour is a description of an experiment
o a behaviour can be sampled (performing the experiment), yielding a current value and a residual behaviour (the latter replaces the original behaviour)
o the results of measurements can be broadcast and observed via behavioural channels (a channel observer simply behaves as the channel source behaviour, with a slight delay)
That’s it! The is no special role for time at all. One can establish local clocks, one can even broadcast their ticking behaviours. But one cannot take an arbitrary absolute time and ask for the value of a behaviour at that time (other than actually running that behaviour forward or backward from “now”).
Also, there is a natural distinction between describing and running a behaviour, with the ability to refer to either the description or to sample outcomes. And having the same behaviour description on both sides of an event in a stepper/until does not mean that nothing changes at the step: the second copy doesn’t continue where the first left off, but starts from its own beginning (with no special tricks to achieve this).
Well, there were lots of negatives as well (eg FunWorlds was an “engine-exposed” workbench rather than a user-directed library), but I thought I’d try to get you interested first!-)
Slides, draft papers (there were two versions), old source snapshots and examples here:
http://www.cs.kent.ac.uk/~cr3/funworlds/
I don’t know how much time I’d be able to spend on this at the moment, but I’d be interested to revive FunWorlds, and share/reuse code/ideas. There was nothing special about my scenegraph, and if you were to drop the special role of external time, your new behaviour/event approach isn’t too far away from what I’d like to see (your Futures, like my behavioural channels, work via MVar updates behind the scenes, right?). Though it seems that each of your packages has more dependencies than FunWorlds had modules..
Ps. Those of your readers interested in FRP history might find the bits about ActiveVRML useful that I pieced together for my IFL’2001 paper (FunWorlds/VRML) – unlike you, I wasn’t there, so this was based on VRML mailing list archives at the time.
2 December 2008, 4:56 pmconal:
@claus:
Thanks for the enthusiastic response. I’d like to read your IFL ’02 slides, but I don’t have PowerPoint. Would you post a PDF version?
Those painful symptoms you mention (user parameter, start times, behaviour aging, splitB, …) are exactly my motivation for revisiting the design. My goal, as always, is to have a simple and compelling denotational semantics — I guess what you call “the semantic ideal” — and to solve all of those problems. I think it will work out this time.
I’ll keep blogging about the various pieces, so stay tuned.
2 December 2008, 6:05 pmclaus:
I’ve added a PDF version of the IFL’2002 slides (MS also used to distribute a free PowerPoint Viewer, which I’ve found very useful whenever I don’t have access to PowerPoint). Couldn’t see an option to translate the inslide transitions to separate pages, so there is some overlap on the first few slides.
I’ve also updated the source snapshot to build with current ghcs.
Both at http://www.cs.kent.ac.uk/~cr3/funworlds/
One problem with those painful issues is that they are not apparent – library designers work around them, users don’t run into them immediately and, when they do, assume that it is just their lack of experience. Only when someone tries to explain their reactive programs in detail, those issues start to stick out from under the rug (as in the tutorial that led to splitB;-).
Perhaps more users could be encouraged to document their experiences in writing reactive programs, this time around (I know of only one such study for Fran: Simon Thompson’s lift simulation, http://www.cs.kent.ac.uk/pubs/1998/583/index.html, which led me to try that problem with my library, for comparison – see examples). It might well help to spot design issues early – not to mention that it is encouraging for the library authors!-)
Btw, is there a general FRP list? I know of the yampa and reactive mailing lists, but those seem to be library-specific.
3 December 2008, 3:24 amRaoul Duke:
@claus, conal
here’s something i find compelling in the way you folks talk: you seem to have a feeling for how things are difficult and not really fitting together well in the end. that’s something i find sadly missing from most development (not just software development) in the world. there’s probably something like 3 stages: those folks who don’t even notice the friction; those who do but then say “we don’t have time” or “i don’t have the solution, and dunno that i would ever be educated enough to find it” (e.g. me); and those who actually can take a stab at it (e.g. you). thanks for taking the stabs.
3 December 2008, 1:06 pmRaoul Duke:
Q: there is a history of a range of functional-reactive systems (yampa, fr time, etc.). might you know / proffer some thoughts on how they compare? i assume some differ in fundamental ways (e.g. discrete vs. continuous), whereas some differ more in terms of what language they are in, or if they are still maintained.
in other words, if i were to start doing frp now, what would you recommend as a long-term usable thing, e.g. with a community behind it? fr. time maybe?
gracias.
8 December 2008, 4:45 pmjake:
I’m new to FRP as well and would love it if you could address Raoul Duke’s question above. Also: how do your ideas relate to synchronous dataflow languages like Lucid Synchrone? What about methodologies for dealing with events? I’m trying to piece together the relationships between several different areas of research: FRP, synchronous languages, partial order event tracing / application monitoring, and event stream processing / CEP. I see significant commonalities between them, but they are all coming from different research communities (functional programming, hard real-time systems, distributed debugging, and DBMS / business intelligence, respectively) and there appears to be little or no dialogue between those communities.
9 December 2008, 9:12 amJake McArthur:
Did you ever pursue this much further? I’m very curious, as I have been looking into comonadic approaches myself (although my most recent approach is not primarily comonadic).
19 June 2009, 2:18 pmconal:
Hi Jake. I pursued comonadic, relative-time, finite-duration FRP just a bit further in Sequences, streams, and segments and in Sequences, segments, and signals and then got distracted by automatic differentiation and functional GPU programming. It’s on my list of things to come back to.
19 June 2009, 2:30 pmJake McArthur:
Years later, I’m looking at relative time FRP again.
Relative time futures seem really weird to me. It seems that they cannot be used as an interface to the real world, because the real world would behave differently depending on what time you observe it. You end up having to abandon caching (implementors everywhere cry tears of joy), and then you end up with some IO-action-like thing with no real semantics at all, because the value is different every time you use it.
Maybe all this just means the “foreign interface” still makes more sense with absolute time semantics, and at runtime you just start your relative-time program at some point on the real-world timeline.
Is this an area of relative time FRP you have thought much about?
27 April 2015, 5:22 amJake McArthur:
Thinking about it more, I guess it’s not totally weird. I was thinking the only way for it to work would be to observe the world all over again, when reusing values describing the world, but another way to interpret it is just that the value is cached, just like in absolute time, and replayed at a delay if you use it later. This actually seems less error prone, in fact, than the absolute time equivalent, since with absolute time you might be accumulating history without even realizing it (until you start having resource issues); with relative time you would see the delay, if you made that mistake.
29 April 2015, 5:00 am